package UnionFind;

public class _547_FriendCircles {
    private int id[];
    private int count;
    private int N;
    public int findCircleNum(int[][] M) {
        this.N = M.length;
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if (M[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        return count;
    }

    public int count(){
        return count;
    }

    public int find(int p) {
        return id[p];
    }

    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        if(pid==qid) return;
        for (int i = 0; i < N; i++) {
            if (id[i] == qid) {
                id[i] = pid;
            }
        }
        count--;
    }
}
